#include "stdio.h"
#include "string.h"
#include "stdlib.h"

struct heap_data
{
    int value;
	int count;
	int seq;
};

typedef struct heap_array
{
    int size;
    int count;
	struct heap_data *root;
}heap_array;

heap_array *heap_array_create(int data_count)
{
    heap_array *ha = malloc(sizeof(heap_array));
	if (data_count == 0)
	    ha->root = NULL;
	else
	    ha->root = malloc(data_count * sizeof(struct heap_data));
	ha->count = 0;
	ha->size = data_count;

	return ha;
}

heap_array *heap_array_destroy(heap_array *ha)
{
    if (ha->root)
	   free (ha->root);
    free(ha);
}
void heap_array_insert(heap_array *ha, int value, int seq)
{
    if (ha->count == ha->size)
	{
	    struct heap_data *new_root = malloc(2 * ha->size * sizeof(struct heap_data));
		if (!new_root)
		    return;
		memcpy(new_root, ha->root, ha->size * sizeof(struct heap_data));
		free(ha->root);
		ha->root = new_root;
		ha->size *= 2;
	}
     	
    struct heap_data *mydata = ha->root;
    int i = 0;
	for (; i < ha->count; i++)
	    if ((mydata + i)->value == value)
		     break;
	if (i < ha->count)
	{
	    if ((mydata + i)->seq < seq) 
		{
		   (mydata + i)->seq = seq;
		   (mydata + i)->count++;
		}
    }
    else
	{
	    (mydata + ha->count)->value = value;
	    (mydata + ha->count)->count = 1;
	    (mydata + ha->count)->seq = seq;
	    ha->count++;
	}
}

int heap_array_get_real_count(heap_array *ha)
{
    struct heap_data *mydata = ha->root;
	int i = 0;
	for (; i < ha->count; i++)
	    if ((mydata + i)->count == 0)
		     break;
	return i;
}
void heap_data_swap(struct heap_data *d1, struct heap_data *d2)
{
     struct heap_data temp;
	 temp.value = d1->value;
	 temp.count = d1->count;
	 temp.seq = d1->seq;

	 d1->value = d2->value;
	 d1->count = d2->count; 
	 d1->seq = d2->seq; 

	 d2->value = temp.value;
	 d2->count = temp.count;
	 d2->seq = temp.seq;
}

void heap_array_print(heap_array *myarray)
{
    struct heap_data *mydata = myarray->root; 
    int i;
	printf("value\tcount\tsequence\n");
	for (i = 0; i < myarray->count; i++)
	    printf("%5d\t%5d\t%5d\n", (mydata + i )->value, (mydata + i)->count, (mydata + i)->seq);
	printf("\n");
}

heap_data_set(struct heap_data *h1, struct heap_data *h2)
{
    h1->value = h2->value;
	h1->count = h2->count;
	h1->seq = h2->seq;
}
void heap_array_quick_sort(heap_array *myarray, int low, int high)
{
    if (low >= high)
	    return;

    struct heap_data *mydata = myarray->root;
    struct heap_data temp;
	heap_data_set(&temp, mydata + low);

	int i = low;
	int j = high - 1;
	for (; i < j;)
	{
	    for (; j > i; j--)
		    if ((mydata + j)->count > temp.count)
			    break;
		    else if ((mydata + j)->count == temp.count)
			{
			     if ((mydata + j)->seq > temp.seq)
				     break;
			}
	    heap_data_set(mydata + i, mydata + j);

        for (; i < j; i++)	
            if ((mydata + i)->count < temp.count)
	    	    break;
		    else if ((mydata + i)->count == temp.count)
			{
			     if ((mydata + i)->seq < temp.seq)   
				     break;
			}
	    heap_data_set(mydata + j, mydata + i);

	    if (i == j)
		    heap_data_set(mydata +j , &temp);

	}
	heap_array_quick_sort(myarray, low, j);
	heap_array_quick_sort(myarray, j + 1, high);
}

heap_array *heap_array_create_from_file(const char *filename)
{
    FILE *fp = fopen(filename, "r");
	if (!fp)
	{
	    printf("file not exists!\n");
	    return NULL;
    }
	char *line = NULL;
	size_t num = 0;
	heap_array *ha = heap_array_create(100);
	int seq = 1;
	while (getline(&line, &num, fp) != -1)
	{
		char *token ;
		char *p = line;
		while (1)
		{
		    token = strchr(p, ' ');
			if (!token)
			{
				//heap_array_insert(ha, atoi(p), seq);
				//seq++;
			    break;
		    }
		    char *q = p;
		    *token = '\0';

			heap_array_insert(ha, atoi(q), seq);
			p = token + 1;
			seq++;
		}
	}
    return ha;
}
int main()
{
    const char *filename = "data.txt";
    heap_array *myarray = heap_array_create_from_file(filename);
	heap_array_print(myarray);
	
    heap_array_quick_sort(myarray, 0, myarray->count);	
	heap_array_print(myarray);
	heap_array_destroy(myarray);
	return 0;
}
